package 剑指offer第2版;

import java.util.Stack;

public class 剑指Offer包含min函数的栈 {
    private static class MinStack {

        /** initialize your data structure here. */
        /**
         测试数据：3,2,1,2,3,4,6,7,1
         stack1执行push操作3 >3
         stack2>push 3

         stack1执行push操作2 3,2
         stack2 3,2

         stack1执行push操作1 3,2,1
         stack2 3,2,1

         stack1执行push操作2 3,2,1,3
         stack2push2的之后发现顶部元素比当前元素大，所以不push
         stack2 3,2,1

         1，定义两个栈，stack1为正常的栈,stack2其中一个栈为最小元素的栈
         2，push操作就是

         **/
        Stack<Integer> s1=null;
        Stack<Integer> s2=null;
        public MinStack() {
            s1=new Stack();
            s2=new Stack();
        }

        public void push(int x) {
            s1.push(x);
            //如果s2中的栈顶的元素比x小则不需push
            if(s2.isEmpty() || s2.peek()>=x){
                s2.push(x);
            }
        }

        public void pop() {
            Integer x=s1.pop();
            if(x.equals(s2.peek())){
                s2.pop();
            }
        }

        public int top() {
            return s2.pop();
        }

        public int min() {
            if(!s2.isEmpty()){
                return s2.peek();
            }
            return 0;
        }

        public static void main(String[] args) {
            MinStack minStack=new MinStack();
            minStack.push(512);
            minStack.push(-1024);
            minStack.push(-1024);
            minStack.push(512);
            minStack.pop();
            System.out.println(minStack.min());
            minStack.pop();
            System.out.println(minStack.min());
            minStack.pop();
            System.out.println(minStack.min());
        }
    }
}
